package leetcode_300;



/**
 *@author 周杨
 *CountPrimes_204 计算所有小于n的素数个数 用筛选法 会浪费空间
 *describe:AC 91%
 *2018年6月11日 下午6:07:58
 */
public class CountPrimes_204 {

	public static void main(String[] args) {
		CountPrimes_204 test=new CountPrimes_204();
		System.out.println(test.countPrimes(5));
		System.out.println(test.countPrimes(6));
		System.out.println(test.countPrimes(7));
		System.out.println(test.countPrimes(8));

	}
	
	/**
	 * describe:6n+1法  所有数都能表示为6n+1 或者6n-1 超时
	 * 2018年6月11日 下午6:06:01
	 */
	public int countPrimes(int n) {
		int res=2;
		if(n<=2)
			return 0;
		if(n==3)
			return 1; 
		for(int i=6; i-1<n; i+=6){          
            if(i<6){  
                res+=2;
                continue;  
            }  
            for(int j=-1; j<=1; j+=2){  
                if(i+j<n&&isPrime(i+j)){  
                    ++res; 
                }  
            }            
        }  
		return res;
    }
	
  
	public static boolean isPrime(int n){  
        for(int i=2; i*i<=n; i++){  
            if(n%i==0){  
                return false;  
            }  
        }  
        return true;  
	}
	
	
	/**
	 * describe:埃拉托色尼筛法。 AC 91%
	 * 2018年6月11日 下午6:07:25
	 */
	public int countPrimes1(int n) {
        if (n <= 1) {
            return 0;
        }

        // 默认所有的元素值都会设置为false
        boolean[] notPrime = new boolean[n];
        notPrime[0] = true;
        notPrime[1] = true;

        for (int i = 2; i * i < n; i++) {
            // 如果i是一个质数，i将i的倍数设置为非质数
            // 如是i是一个合数，则它必定已经设置为true了，因为是从2开始处理的
            if (!notPrime[i]) {
                for (int j = 2 * i; j < n; j += i) {
                    notPrime[j] = true;
                }
            }
        }

        // 统计质数的个数
        int result = 0;
        for (boolean b : notPrime) {
            if (!b) {
                result++;
            }
        }

        return result;
    }

}
